Union Find
頂点を辺で繋いでいってグループに分けるやつ。「素集合データ構造」とも呼ばれるらしい
正確にはUnion Findというアルゴリズムで管理するデータ構造を素集合データ構造と呼ぶ感じ？
Union Find
競プロで最初に出会う天才アルゴリズム
概要
find(x) : $ x のいるグループの根を取得する$ O(\alpha(N))
union(x, y) : 2点$ x, y を連結する$ O(\alpha(N))
$ \alpha(x)はアッカーマン関数の逆関数。突然巨大数論の関数が出てくるの好き 実装
unionをrankを元に連結してるが、sizeを元にする方法もある。計算量はどちらでも変わらない
code:UF.py
class UnionFind:
def __init__(self, n):
self.parents = list(range(n))
def find(self, x):
return x
else:
self.parentsx = self.find(self.parentsx) # 経路圧縮 def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y: return # すでに同じグループ
if self.rankx < self.ranky: x, y = y, x
self.parentsy = x # ランクを元に合体 if self.rankx == self.ranky: 発展
この方法では最悪計算量が相変わらず$ O(\log N) だが、これを$ O(\log N / \log \log N ) に抑える方法もあるらしい
（競プロ文脈では分母の$ \log \log N が小さすぎて、実際の速度はあまり変わらない気がするが……）
参考
ポテンシャルUnion Find
概要
各ノード間の距離も記録するUnion Find
find(x) : $ x のいるグループの根を取得する$ O(\alpha(N))
union(x, y, w) : weight(y) - weight(x) = wとなるよう、2点$ x, y を連結する$ O(\alpha(N))
diff(x, y) : $ x, y の距離weight(y) - weight(x)を取得する$ O(\alpha(N))
union(x, y, w)でw = 0とすればただのUnion Findと同じになる
実装
根との差diff_weightを使ってひと手間加える。
code:potentialUF.py
class PotentialUnionFind:
def __init__(self, n):
self.parents = list(range(n))
def find(self, x):
return x
else:
r = self.find(self.parentsx) # 経路圧縮 self.diff_weightx += self.diff_weight[self.parentsx] # 圧縮分の効果 return r
def union(self, x, y, w):
w += self.weight(x) - self.weight(y) # xの根→yの根のあるべき値
x = self.find(x)
y = self.find(y)
if x == y: return False # すでに同じグループ
if self.rankx < self.ranky: x, y = y, x
w = -w
self.parentsy = x # ランクを元に合体 if self.rankx == self.ranky: return True
def weight(self, x):
self.find(x)
def diff(self, x, y):
return self.weight(y) - self.weight(x)
すでに同じグループなx, yに対するunion(x, y, w)や、異なるグループなx, yに対するdiff(x, y)はお好みで調整するといい感じ
問題
発展
「ポテンシャルはアーベル群ならOK」とか「牛ゲーとの関連」とかあるらしい
参考
関係式つきUnion Find
概要
各ノード間の1次式な関係を記録するUnion Find
find(x) : $ x のいるグループの根を取得する$ O(\alpha(N))
union(x, y, a, b) : value(y) = a * value(x) + bとなるよう、2点$ x, y を連結する$ O(\alpha(N))
getValue(x) : value(x)の取りうる値を取得する（複数・一意・矛盾）
getRelation(x, y) : value(x),(y)が確定してないとき、value(y) = a * value(x) + bなるa, bがあれば取得する
union(x, y, a, b)でa = 1とすればポテンシャルUnion Findと同じになる
実装
各頂点$ i について親頂点$ p_i との関係式$ v_i = a_iv_{p_i}+b_iと、グループの値の確定状況とその値を根に記録しておく。
find(x)
経路圧縮ついでに親$ p の根$ r との関係式$ v_p = a_pv_r+b_p と、自身の親との関係式$ v_x = a_xv_p+b_xから、
$ v_x = (a_xa_p)v_r+(a_xb_p+b_x)
と更新する。
union(x, y, a, b)
各グループの値の確定状況から、合体後の確定状況も変わってくる
異なるグループ間の関係式の更新
$ x の根に$ y の根を接続するときを考える
$ x, y を逆にするとき
$ v_x = \frac{1}{a}v_y-\frac{b}{a}
頂点$ x の根$ r_x との関係式$ v_x = a_xv_{r_x}+b_x
頂点$ y の根$ r_y との関係式$ v_y = a_yv_{r_y}+b_y
頂点$ x と頂点$ y の満たしてほしい関係式$ v_y = av_x + b
から、根$ r_x と根$ r_y の関係式$ v_{r_y} = Av_{r_x}+B の係数$ A, B を求めると、
$ v_{r_y} = \frac{aa_x}{a_y}v_{r_x}+\frac{ab_x+b-b_y}{a_y}
となる
同じグループ間での関係式の更新
すでにある関係式$ v_y = a'v_x + b' と新しい関係式$ v_y = av_x + b から、
$ v_x = -\frac{b - b'}{a - a'}
となる
$ a - a' = 0 のとき、$ b - b' = 0 なら更新なし、$ b - b' \not= 0 なら矛盾
$ a - a' \not= 0 なら$ v_x, v_y の値確定
getRelation(x, y)
$ x, y の共通の根$ r との関係式$ v_x = a_xv_r + b_x と$ v_y = a_yv_r + b_y から、
$ v_y = \frac{a_y}{a_x}v_x + \frac{a_xb_y - a_yb_x}{a_x}
を得る
係数としては$ \mathbb{Z}/p\mathbb{Z}やa = 1限定の$ \mathbb{Z}が使える。理論上は$ \mathbb{R}も行けるが、演算誤差的にアレ
補足 : $ \mathbb{Q} の代わりに$ \mathbb{Z}/p\mathbb{Z} を使った。$ p の値によってはWAになる。実用上は衝突の誤判定を回避するため、複数の素数modで検証したほうがいい。
高速化の余地かなりあると思うが、動くものを作るので精一杯だった！
この問題で使ってない部分バグってるかもしれん
問題
（概要：「$ 1 個のアイテム$ A_i と$ x_i 個のアイテム$ B_i が交換できるとき、無限にアイテムを増やす手段がある場合は"No"を、大丈夫なら"Yes"を出力してね」）
参考
削除可能Union-Find
従来のUnion-Findは削除する操作に弱い。